#include <bits/stdc++.h>

using namespace std;

// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort-list/

// 不需要提交这个类
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 提交这个类即可
// 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
// 注意为了额外空间复杂度O(1)，所以不能使用递归
// 因为mergeSort递归需要O(log n)的额外空间
class Solution 
{
public:
	// 包括s在内，往下数k个节点返回
	// 如果不够，返回最后一个数到的非空节点
    ListNode* findEnd(ListNode* s, int k)
    {
        while(--k != 0 && s->next != nullptr)
        {
            s = s->next;
        }
        return s;
    }

    // 将两个有序链表合并成一个有序链表后，链表的
    // 头节点保存在 start 中，尾节点保存在 end 中
    ListNode *start; 
    ListNode *end;

	// l1...r1 -> null : 有序的左部分
	// l2...r2 -> null : 有序的右部分
	// 整体merge在一起，保证有序
	// 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾
    void merge(ListNode* l1, ListNode* r1, ListNode* l2, ListNode* r2)
    {
        ListNode *pre;
        // 先拿一个节点作为头结点
        if(l1->val <= l2->val)
        {
            start = l1;
            pre = l1;
            l1 = l1->next;
        }
        else
        {
            start = l2;
            pre = l2;
            l2 = l2->next;
        }
        // 两个有序链表的合并，采取尾插的方式
        while(l1 && l2)
        {
            if(l1->val <= l2->val)
            {
                pre->next = l1;
                pre = l1;
                l1 = l1->next;
            }
            else
            {
                pre->next = l2;
                pre = l2;
                l2 = l2->next;
            }
        }
        // 记录合并后的尾节点
        if(l1)
        {
            pre->next = l1;
            end = r1;
        }
        else
        {
            pre->next = l2;
            end = r2;
        }
    }

    ListNode* sortList(ListNode* head) 
    {
        int n = 0;
        ListNode *cur = head;
        while(cur)
        {
            ++n;
            cur = cur->next;
        }
        // l1...r1 每组的左部分
		// l2...r2 每组的右部分
		// next 下一组的开头
		// lastTeamEnd 上一组的结尾
        ListNode *l1, *r1, *l2, *r2, *next, *lastTeamEnd;
        for(int step = 1; step < n; step <<= 1)
        {
            // 第一组很特殊，因为要决定整个链表的头，所以单独处理
            l1 = head;
            r1 = findEnd(l1, step);
            // 能够进入 for 循环，那么 l2 和 r2 一定是不为 null 的
            l2 = r1->next;
            r2 = findEnd(l2, step);
            next = r2->next;
            // 让 r1->next 和 r2->next 都指向 null，然后
            // 进行 l1...r1 和 l2...r2 这两个链表的合并
            r1->next = nullptr;
            r2->next = nullptr;
            merge(l1, r1, l2, r2);
            // 将整个链表的开头保存在 head 中
			head = start;
			lastTeamEnd = end;
            while(next)
            {
                // 处理下一组的合并
                l1 = next;
                // r1 一定不为 null
                r1 = findEnd(l1, step);
                // 看看有没有下一组了
                l2 = r1->next;
                // 每下一组
                if(l2 == nullptr) 
                {
                    lastTeamEnd->next = l1;
                    break;
                }
                // 有下一组
                r2 = findEnd(l2, step);
                next = r2->next;
                r1->next = nullptr;
                r2->next = nullptr;
                merge(l1, r1, l2, r2);
                // 上一组的尾节点指向合并后的头节点
                lastTeamEnd->next = start;
                lastTeamEnd = end;
            }
        }
        return head;
    }
};


// 提交这个类即可
// 时间复杂度O(n*logn)，额外空间复杂度O(logn)，有稳定性
// mergeSort递归需要O(log n)的额外空间
class Solution 
{
private:
    // 合并两个有序链表，并将合并后的头节点返回
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        if(!head1 || !head2) return head1 ? head1 : head2;

        // 先拿出一个节点来作为链表的头节点
        ListNode *newHead = head1->val <= head2->val ? head1 : head2;
        ListNode *tail = newHead;
        head1->val <= head2->val ? head1 = head1->next : head2 = head2->next;
        while(head1 && head2)
        {
            // 尾插法
            if(head1->val <= head2->val)
            {
                tail->next = head1;
                head1 = head1->next;
            }
            else
            {
                tail->next = head2;
                head2 = head2->next;
            }
            tail = tail->next;
        }
        tail->next = head1 ? head1 : head2;
        return newHead;
    }

    // 以 head->...->tail 这个链表的中间节点作为划分
    // 点将链表划分成两个链表
    ListNode* mergeSort(ListNode* head, ListNode* tail)
    {
        if(head == nullptr) return head;
        if(head->next == tail)
        {
            head->next = nullptr;
            return head;
        }
        // 找出链表的中间节点，记为 slow
        ListNode *slow = head, *fast = head;
        while(fast != tail && fast->next != tail)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // slow 作为前一个链表的尾节点，作为后一个链表的头结点
        // merge 合并两个有序的链表，并将合并后的头节点返回
        return merge(mergeSort(head, slow), mergeSort(slow, tail));
    }

public:
    ListNode* sortList(ListNode* head) 
    {
        return mergeSort(head, nullptr);
    }
};